package domains;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import config.GlobalConfig;
import java.util.HashMap;
import java.util.Map;
import controlFlowGraph.*;

public class AvailableExpressionsAnalysis extends Analysis {

	// Transformation things

	/**
	 * Map non trivial expressions to temporary variables (needed for Available
	 * Expressions)
	 */
	public static Map<Expression, Variable> expressionToTemporary = new HashMap<Expression, Variable>();

	public static int temporaryCounter = 1;

	public static int nodeCounter = -2;

	private CFGNode splitEdges(CFGEdge edge, Expression exp) {
		// Create temporary node
		CFGNode n = edge.getFromNode();
		CFGNode tmpNode = new CFGNode(AvailableExpressionsAnalysis.nodeCounter--);
		edge.setFromNode(tmpNode);
		Variable tmpv = null;
		if (AvailableExpressionsAnalysis.expressionToTemporary.get(exp) != null) {
			tmpv = AvailableExpressionsAnalysis.expressionToTemporary.get(exp);
		} else {
			tmpv = new Variable("tmpVar"+ AvailableExpressionsAnalysis.temporaryCounter++);
			AvailableExpressionsAnalysis.expressionToTemporary.put(exp, tmpv);
			GlobalConfig.variableSet.add(tmpv);
		}

		// Adjust edges
		CFGEdge newEdge = new CFGEdge(n, tmpNode,
				new LabAssign(tmpv,exp));
		n.clearOutEdges();
		n.addOutEdge(newEdge);
		tmpNode.addInEdge(newEdge);
		tmpNode.addOutEdge(edge);
		return tmpNode;
	}
	
	private void replaceExpressionsByVariables(CFGLabel lab) {
		if (lab instanceof LabAssign) {
			LabAssign work = (LabAssign) lab;
			if (!work.getRightSide().isTrivial()) {
				work.setRightSide(AvailableExpressionsAnalysis.expressionToTemporary.get(work.getRightSide()));
			}
		} else if (lab instanceof LabLoad) {
			LabLoad work = (LabLoad) lab;
			if (!work.getRightSide().isTrivial()) {
				work.setRightSide(AvailableExpressionsAnalysis.expressionToTemporary.get(work.getRightSide()));
			}
		} else if (lab instanceof LabStore) {
			LabStore work = (LabStore) lab;
			if (!work.getRightSide().isTrivial()) {
				work.setRightSide(AvailableExpressionsAnalysis.expressionToTemporary.get(work.getRightSide()));
			}
			if (!work.getLeftSide().isTrivial()) {
				work.setLeftSide(AvailableExpressionsAnalysis.expressionToTemporary.get(work.getLeftSide()));
			}
		} else if (lab instanceof LabPos) {
			LabPos work = (LabPos) lab;
			if (!work.getCondition().isTrivial()) {
				work.setCondition(AvailableExpressionsAnalysis.expressionToTemporary.get(work.getCondition()));
			}
		} else if (lab instanceof LabNeg) {
			LabNeg work = (LabNeg) lab;
			if (!work.getCondition().isTrivial()) {
				work.setCondition(AvailableExpressionsAnalysis.expressionToTemporary.get(work.getCondition()));
			}
		}
	}
	
	@Override
	public void preTransformCFG(CFG cfg) {
		List<CFGNode> newNodes = new ArrayList<CFGNode>();
		for (CFGNode n : cfg.getAllNodes()) {
			if (n.getId() != -1) {

				CFGEdge edge = n.getOutEdges().get(0);
				if (edge.getLabel() instanceof LabAssign) {
					if (((LabAssign) edge.getLabel()).getRightSide().isTrivial()) {
						// Nothing to do
					} else {
						// Take expression we are talking about
						Expression theRightSide = ((LabAssign) edge.getLabel()).getRightSide();
						newNodes.add(this.splitEdges(edge, theRightSide));
						replaceExpressionsByVariables(edge.getLabel());
					}
				} else if (edge.getLabel() instanceof LabLoad) {
					if (((LabLoad) edge.getLabel()).getRightSide().isTrivial()) {
						// Nothing to do
					} else {
						// Take expression we are talking about
						Expression theRightSide = ((LabLoad) edge.getLabel()).getRightSide();
						newNodes.add(this.splitEdges(edge, theRightSide));
						replaceExpressionsByVariables(edge.getLabel());
					}
				} else if (edge.getLabel() instanceof LabStore) {
					if (((LabStore) edge.getLabel()).getRightSide().isTrivial()) {
						// Nothing to do
					} else {
						// Take expression we are talking about
						Expression theRightSide = ((LabStore) edge.getLabel()).getRightSide();
						
						newNodes.add(this.splitEdges(edge, theRightSide));
					}
					if (((LabStore) edge.getLabel()).getLeftSide().isTrivial()) {
						// Nothing to do
					} else {
						// Take expression we are talking about
						Expression theLeftSide = ((LabStore) edge.getLabel()).getLeftSide();

						newNodes.add(this.splitEdges(edge, theLeftSide));
					}
					replaceExpressionsByVariables(edge.getLabel());
					
				} else if (edge.getLabel() instanceof LabPos) {
					if (((LabPos) edge.getLabel()).getCondition().isTrivial()) {
						// Nothing to do
					} else {
						// Take expression we are talking about
						Expression theRightSide = ((LabPos) edge.getLabel()).getCondition();
						// Don't forget the Neg Case
						List<CFGEdge> res = new ArrayList<CFGEdge>();
						res.addAll(edge.getFromNode().getOutEdges());
						res.remove(edge);
						CFGEdge neg = res.get(0);
						
						CFGNode tmpNode = this.splitEdges(edge, theRightSide); 
						neg.setFromNode(tmpNode);
						tmpNode.addOutEdge(neg);
						newNodes.add(tmpNode);
						replaceExpressionsByVariables(edge.getLabel());
						replaceExpressionsByVariables(neg.getLabel());
					}
				} else {
					// No transformation
				}
			}
		}
		for (CFGNode newn : newNodes) {
			cfg.addCFGNode(newn);
		}
		if (GlobalConfig.debug) {
			System.out.println(AvailableExpressionsAnalysis.expressionToTemporary);;
		}
	}

	@Override
	public void postTransformCFG(CFG cfg) {
		for (CFGNode node : cfg.getAllNodes()) {
			AvailableExpressions info = (AvailableExpressions) node.getAnalysisInfo();
			for (CFGEdge edge : node.getOutEdges()) {
				if (edge.getLabel() instanceof LabAssign) {
					LabAssign lab = (LabAssign) edge.getLabel();
					if (info.getAvailExpr().contains(lab.getRightSide())) {
						edge.setLabel(new LabNop());
					}
				}
			}
		}
	}
	
	@Override
	public AnalysisDomain getBottom() {
		return new AvailableExpressions(GlobalConfig.expressionSet);
	}

	@Override
	public AnalysisDomain getTop() {
		return new AvailableExpressions(new HashSet<Expression>());
	}

	@Override
	public AnalysisDomain join(AnalysisDomain left, AnalysisDomain right) {
		AvailableExpressions l = (AvailableExpressions) left;
		AvailableExpressions r = (AvailableExpressions) right;
		Set<Expression> res = new HashSet<Expression>();
		res.addAll(l.getAvailExpr());
		res.retainAll(r.getAvailExpr());
		return new AvailableExpressions(res);
	}

	@Override
	public AnalysisDomain meet(AnalysisDomain left, AnalysisDomain right) {
		AvailableExpressions l = (AvailableExpressions) left;
		AvailableExpressions r = (AvailableExpressions) right;
		Set<Expression> res = new HashSet<Expression>();
		res.addAll(l.getAvailExpr());
		res.addAll(r.getAvailExpr());
		return new AvailableExpressions(res);
	}

	@Override
	public AnalysisDomain widening(AnalysisDomain left, AnalysisDomain right) {
		AvailableExpressions l = (AvailableExpressions) left;
		AvailableExpressions r = (AvailableExpressions) right;
		Set<Expression> res = new HashSet<Expression>();
		res.addAll(l.getAvailExpr());
		res.retainAll(r.getAvailExpr());
		return new AvailableExpressions(res);
	}

	@Override
	public AnalysisDomain narrowing(AnalysisDomain left, AnalysisDomain right) {
		AvailableExpressions l = (AvailableExpressions) left;
		AvailableExpressions r = (AvailableExpressions) right;
		Set<Expression> res = new HashSet<Expression>();
		res.addAll(l.getAvailExpr());
		res.addAll(r.getAvailExpr());
		return new AvailableExpressions(res);
	}

	@Override
	public String printNode(CFGNode node) {
		Set<Expression> set = ((AvailableExpressions) node.getAnalysisInfo())
				.getAvailExpr();
		String res = "";
		if (node.getId() == 0 || node.getId() == -1) {
			if (node.getId() == 0) {
				res += "START : {";
			} else {
				res += "END : {";
			}
		} else {
			res = "P" + node.getId() + " : {";
		}
		String[] expressions = new String[set.size()];
		int i = 0;
		for (Expression e : set) {
			expressions[i] = e.toString();
			i++;
		}
		Arrays.sort(expressions);
		int size = set.size();
		for (String s : expressions) {
			res += s;
			if (size > 1) {
				res += ", ";
				size--;
			}
		}
		res += "}";
		return res;
	}

	@Override
	public AnalysisDomain edgeEffectNOP(CFGEdge edge) {
		return edge.getFromNode().getAnalysisInfo();
	}

	@Override
	public AnalysisDomain edgeEffectPos(CFGEdge edge) {
		Set<Expression> res = new HashSet<Expression>();
		res.addAll(((AvailableExpressions) edge.getFromNode().getAnalysisInfo())
				.getAvailExpr());
		res.addAll(edge.getLabel().getInvolvedExpressions());
		return new AvailableExpressions(res);
	}

	@Override
	public AnalysisDomain edgeEffectNeg(CFGEdge edge) {
		Set<Expression> res = new HashSet<Expression>();
		res.addAll(((AvailableExpressions) edge.getFromNode().getAnalysisInfo())
				.getAvailExpr());
		res.addAll(edge.getLabel().getInvolvedExpressions());
		return new AvailableExpressions(res);
	}

	@Override
	public AnalysisDomain edgeEffectAssign(CFGEdge edge) {
		Set<Expression> res = new HashSet<Expression>();
		res.addAll(((AvailableExpressions) edge.getFromNode().getAnalysisInfo())
				.getAvailExpr());
		res.addAll(edge.getLabel().getInvolvedExpressions());
		res.removeAll(getExpressionWithVar(((LabAssign) edge.getLabel())
				.getLeftSide()));
		return new AvailableExpressions(res);
	}

	@Override
	public AnalysisDomain edgeEffectLoad(CFGEdge edge) {
		Set<Expression> res = new HashSet<Expression>();
		res.addAll(((AvailableExpressions) edge.getFromNode().getAnalysisInfo())
				.getAvailExpr());
		res.addAll(edge.getLabel().getInvolvedExpressions());
		res.removeAll(getExpressionWithVar(((LabLoad) edge.getLabel())
				.getLeftSide()));
		return new AvailableExpressions(res);
	}

	@Override
	public AnalysisDomain edgeEffectStore(CFGEdge edge) {
		Set<Expression> res = new HashSet<Expression>();
		res.addAll(((AvailableExpressions) edge.getFromNode().getAnalysisInfo())
				.getAvailExpr());
		res.addAll(edge.getLabel().getInvolvedExpressions());
		return new AvailableExpressions(res);
	}

	private Set<Expression> getExpressionWithVar(Variable v) {
		Set<Expression> res = new HashSet<Expression>();
		for (Expression exp : GlobalConfig.expressionSet) {
			if (exp.getInvolvedVariables().contains(v)) {
				res.add(exp);
			}
		}
		return res;
	}

	public void removeTrivialExpressions(CFG cfg) {
		for (CFGNode node : cfg.getAllNodes()) {
			Set<Expression> res = new HashSet<Expression>();
			res.addAll(((AvailableExpressions) node.getAnalysisInfo())
					.getAvailExpr());
			for (Expression expr : ((AvailableExpressions) node
					.getAnalysisInfo()).getAvailExpr()) {
				if (expr.isTrivial()) {
					res.remove(expr);
				}
			}
			node.setAnalysisInfo(new AvailableExpressions(res));
		}
	}

}
